package bin_tree.oj;

import java.util.Scanner;

public class KY11 {
    private static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        //构建一个值为val的TreeNode节点
        public TreeNode(char val){
            this.val = val;
        }
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        //获取用户多组输入，需要用while循环
        while(scanner.hasNext()){
            //获取到的是字符串形式的二叉树先序遍历结果
            String Line = scanner.next();
            //要将字符串的每个字符构建为二叉树的节点
            TreeNode root = build(Line);
            //中序遍历二叉树，按照格式打印节点值
            inOrder(root);
            //按要求换行
            System.out.println();
        }
    }

    private static void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //根据先序遍历结果字符串还原二叉树，返回构建后的二叉树的根节点
    private static TreeNode build(String line){
        return preOrderBuild(line);
    }

    //表示处理到哪个字符了
    static int index = 0;
    private static TreeNode preOrderBuild(String line){
        char c = line.charAt(index);
        if(c == '#'){
            return null;
        }
        TreeNode root = new TreeNode(c);
        index ++;
        root.left = preOrderBuild(line);
        index ++;
        root.right = preOrderBuild(line);
        return root;
    }
}